#include <assert.h>

#include <algorithm>
#include <array>
#include <cmath>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>

class Solution {
 public:
  class compare {
   public:
    bool operator()(const std::pair<int, int> &lhs,
                    const std::pair<int, int> &rhs)
    {
      return lhs.second > rhs.second;
    }
  };

  std::vector<int> topKFrequent(std::vector<int> &nums, int k)
  {
    std::unordered_map<int, int> map;
    for (int i : nums) { map[i]++; }

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        compare>
        pri_que;

    for (auto &pair : map)
    {
      pri_que.push(pair);
      if (pri_que.size() > k) { pri_que.pop(); }
    }

    std::vector<int> ret(k);
    for (int i = k - 1; i >= 0; --i)
    {
      ret[i] = pri_que.top().first;
      pri_que.pop();
    }

    return ret;
  }
};
